#include<bits/stdc++.h>
#define rg register
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

const int maxn=1e6+10;

int n,Q;
char S[maxn];
int sum[maxn];

inline int solve(int l,int r)
{
	int Mx=-(int)1e6,Mn=(int)1e6;
	for(rg int i=l-1;i<=r;i+=1)
	{
		Mn=min(Mn,sum[i]);
		Mx=max(Mx,sum[i]-Mn);
	}
	if(sum[l-1]>Mn)Mx=max(Mx,1);
	return sum[l-1]-Mn+Mx-(sum[r]-Mn);
}

int main()
{
//	file("good1");
	scanf("%d %d",&n,&Q);
	scanf("%s",S+1);
	for(rg int i=1;i<=n;i+=1)sum[i]=sum[i-1]+(S[i]=='1'?1:-1);
	int Ans=0;
	while(Q--)
	{
		int l,r;scanf("%d %d",&l,&r);
		int re=solve(l,r);
		Ans^=re;
		cout<<re<<endl;
	}
	cout<<endl;
	printf("%d\n",Ans);
	return 0;
}
